package 剑指offer.树;

import java.util.ArrayList;
import java.util.Stack;

/**
 * TODO practice again
 *
 * 把一棵二叉树的引用按照中序遍历改为双向链表的指向，不能使用辅助空间
 *
 * 解决方案就是把 right 节点作为 next 节点
 * 把 left 节点作为 pre 节点，来改造二叉树
 */
public class 第36题二叉搜索树与双向链表 {


    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /*
        10
     6      14
    4 8   12 16
        十分巧妙的解法：
        一开始就拿到最左节点 4，此时他的上一个节点是 6，
        那么就要有一种机制能够同时保存 4 和 6，也就是代码的第一处
        那么构造 4和6 的指针指向，也就是第 3 处

        然后继续处理下一个节点，必须是右节点因为上面两步已经处理了 L 和 D
        依然是先找到最右边的节点，然后和当前的根节点修改指向，第4与第5处

        关于中间第二处代码的含义：
            递归函数在回溯的时候，一定会路经非叶子节点，
            那么此时应该立刻处理他的右子节点下面的最右叶子节点，
            此时应该把该最右边的节点和当前的根节点相连接，也就是：中序遍历左子树的最后一个节点与根节点连接
     */
    public TreeNode Convert(TreeNode root) {
        if (root == null)
            return null;
        if (root.left == null && root.right == null)
            return root;
        // 1. 中序遍历肯定首先要定位最左边的节点
        TreeNode left = Convert(root.left); // 第一次执行 left 就是最左边的叶子节点
        TreeNode p = left;
        // 2.
        while (p != null && p.right != null) {
            p = p.right;
        }
        // 3. 构造链表的双向引用
        if (left != null) {
            p.right = root;
            root.left = p;
        }
        // 4. 左孩子和根节点已经构成了双向链表，现在处理根节点和他的右孩子。这样才是DLR
        TreeNode right = Convert(root.right);
        // 5. 构造根节点和他的右孩子的双向引用
        if (right != null) {
            right.left = root;
            root.right = right;
        }
        // 本来一开始就把最左边的叶子节点作为了首节点，所以返回链表头结点的时候也要返回这个 left
        // 但是如果二叉树只有一个节点的话就返回 root，此时left为null
        return left != null ? left : root;
    }

    /**
     * 使用辅助空间
     * 借助 right 节点作为 next 引用
     * 把 left 节点作为 pre 引用
     */
    public TreeNode Convert3(TreeNode root) {
        if (root == null)
            return null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        TreeNode pre = null;// 用于保存中序遍历序列的上一节点
        boolean isFirst = true;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            if (isFirst) {
                root = p;// 将中序遍历序列中的第一个节点记为root
                pre = root;
                isFirst = false;
            } else {
                pre.right = p;
                p.left = pre;
                pre = p;
            }
            // 重点，每一次引用关系处理完了之后都要处理右子节点，
            // 因为这样才能保证在回溯时，遇到含有右子节点的情况时，该右子节点可以立即被处理。符合中序遍历的语义
            p = p.right;
        }
        return root;
    }

    /*
       这是使用辅助空间的解法
       用 List 保存 LDR 的遍历结果
       然后添加指针指向
     */
    public TreeNode Convert2(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        ArrayList<TreeNode> list = new ArrayList<>();
        LDR(pRootOfTree, list);
        return JOIN(list);

    }

    // 中序遍历，在list中按遍历顺序保存
    public void LDR(TreeNode pRootOfTree, ArrayList<TreeNode> list) {
        if (pRootOfTree.left != null) {
            LDR(pRootOfTree.left, list);
        }
        list.add(pRootOfTree);
        if (pRootOfTree.right != null) {
            LDR(pRootOfTree.right, list);
        }
    }

    // 遍历list，修改指针。右指针就是 next，左指针就是 pre
    public TreeNode JOIN(ArrayList<TreeNode> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).right = list.get(i + 1);
            list.get(i + 1).left = list.get(i);
        }
        return list.get(0);
    }

}
